Llista encadenada

En el context de la informàtica, una llista encadenada és un estructura de dades fonamental que s'utilitza per implementar altres estructures. Consisteix en una seqüència de nodes on cada node conté les dades d'un element de la llista i un o dos apuntadors o enllaços, un enllaç al node següent, i un enllaç al node posterior.

Les llistes encadenades que tenen un sol enllaç per element s'anomenen llistes encadenades simples i permeten recórrer la llista en un sol sentit.

Les llistes encadenades que tenen dos enllaços per element s'anomenen llistes encadenades dobles i permeten recórrer la llista en tots dos sentits.

S'anomenen llistes encadenades circulars si el primer i l'últim node estan enllaçats. Si estan enllaçats mútuament la llista s'anomena llista encadenada circular doble i si només estan enllaçats en un sentit s'anomena llista encadenada circular simple.

La principal diferència d'una llista encadenada respecte als vectors és que l'ordre dels elements enllaçats pot ser diferent de l'ordre en què s'emmagatzemen els elements a la memòria.

Una llista encadenada és una tipus de dades auto-referenciat, ja que contenen enllaços entre dades del mateix tipus. Les llistes encadenades permeten la inserció, modificació i eliminació de nodes en un punt qualsevol amb un cost computacional constant amb independència de la mida de la llista. En canvi les cerques requereixen un cost computacional que incrementa linealment amb la mida de la llista.

Les llistes encadenades poden ser implementades en múltiples llenguatges. Llenguatges com Lisp o Scheme tenen estructures tipus llista preconstruides. Els llenguatges de programació procedimentals i els llenguatges de programació orientats a objecte com el llenguatge de programació C, C++ o Java també proporcionen llistes.